/*
 * @lc app=leetcode.cn id=76 lang=javascript
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  const n = s.length;

  let minStart = 0;
  let minLen = Infinity;

  const tMap = new Map();
  for (const ch of t) {
    tMap.set(ch, tMap.has(ch) ? tMap.get(ch) + 1 : 1);
  }

  const windowMap = new Map();
  let valid = 0; // 用于记录窗口中满足条件的字符数（只统计是否出现，不统计次数）
  let start = 0;

  for (let end = 0; end < n; end++) {
    const ch = s[end];

    // 更新windowsMap以及valid
    if (tMap.has(ch)) {
      let cnt = (windowMap.get(ch) || 0) + 1;
      windowMap.set(ch, cnt);
      if (cnt === tMap.get(ch)) valid++;
    }

    // 滑动窗口满足合法子串，start开始右移缩小区间
    while (valid === tMap.size) {
      // 更新最小窗口
      if (minLen > end - start + 1) {
        minLen = end - start + 1;
        minStart = start;
      }

      // 检查左元素并更新试图删除左元素后窗口Map的状态
      const leftChar = s[start];
      windowMap.set(leftChar, windowMap.get(leftChar) - 1);

      // 检查缩小后情况
      if (tMap.has(leftChar) && windowMap.get(leftChar) < tMap.get(leftChar))
        valid--;

      // 右移开始边界
      start++;
    }
  }
  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
};
// @lc code=end
